package com.mj.listen3.链表;

public class _86_分隔链表 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        // 准备两个虚拟头节点
        ListNode lHead = new ListNode(0);
        ListNode lTail = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rTail = rHead;

        while (head != null) {
            if (head.val < x) {
                // 往左边链表中链接
                lTail.next = head;
                lTail = lTail.next;
            } else {
                // 往右边链表中链接
                rTail.next = head;
                rTail = rTail.next;
            }
            head = head.next;
        }

        // 拼接两个链表
        lTail.next = rHead.next;

        // 这一步是必须的，因为可能出现这样的情况：
        // 原链表倒数第 N 个节点 A 的值是 >=x 的，A 后面所有节点的值都是 <x 的
        // 然后 rTail.next 最终其实就是 A.next。而 rTail.next 应该为null才对
        rTail.next = null;
        return lHead.next;
    }
}
